package DataStructure.tree.swordOffer;

import DataStructure.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 剑指 Offer 54. 二叉搜索树的第k大节点 https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof
 * 题目简述：给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
 */
public class KthLargest {

    /**
     * 思路一：中序遍历获取所有节点值到list中，然后获取list中倒数第k个元素
     */
    List<Integer> list = new ArrayList<>();
    public int kthLargest(TreeNode root, int k) {
        recurFind(root);
        return list.get(list.size() - k);
    }
    public void recurFind(TreeNode root) {
        if(root == null) return;
        recurFind(root.left);
        list.add(root.val);
        recurFind(root.right);
    }

    /**
     * 思路二：逆序中序遍历（右根左）即为递减序列，遍历到第k个节点返回
     */
    int k,res;
    public int kthLargest2(TreeNode root, int k) {
        this.k = k;
        recur(root);
        return res;
    }
    public void recur(TreeNode root) {
        if (root == null || k == 0) return;
        recur(root.right);
        if (--k == 0) res = root.val;
        recur(root.left);
    }
}
